#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

//int main()
//{
//	int n = 5;
//	int cur = 0, prev = 0;
//	int miss = 0, repeat = 0;
//	
//	for (int i = 0; i < n; ++i)
//	{
//		scanf("%d", &cur);
//
//		if (prev == cur)
//		{
//			repeat = prev;
//			miss = prev + 1;
//			break;
//		}
//
//		prev = cur;
//	}
//
//	printf("%d %d", miss, repeat);
//
//	return 0;
//}

int Search(int* a, int sz)
{
	int left = 0, right = sz - 1;

	while (left <= right)
	{
		int mid = ((right - left) >> 1) + left;

		if (a[mid] != mid)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}

	return left;
}

int Search1(int nums[], int n) 
{
	int start = 0, end = n - 1;

	while (start <= end) 
	{
		int mid = (start + end) / 2;

		if (nums[mid] == mid)
			start = mid + 1;
		else
			end = mid - 1;
	}

	return start;
}

int Search2(int nums[], int n) 
{
	int res = 0;
	for (int i = 0; i < n; i++) 
	{
		res ^= nums[i];
		res ^= i;
	}

	return res ^ n;
}

int Search3(int nums[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		if (nums[i] != i)
			return i;
	}

	return -1;
}

int main()
{
	//int a[] = { 0, 1, 3 };
	//int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 10 };
	int a[] = { 0, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	int ret = Search(a, sz);
	printf("ret:%d\n", ret);

	int ret1 = Search1(a, sz);
	printf("ret1:%d\n", ret1);

	int ret2 = Search2(a, sz);
	printf("ret2:%d\n", ret2);

	int ret3 = Search3(a, sz);
	printf("ret3:%d\n", ret3);

	return 0;
}